package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertionSort {

    public InsertionSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将 arr[i] 插入到合适位置
            // v3
            E temp = arr[i];
            int j;
            for (j = i; j-1 >= 0 && temp.compareTo(arr[j-1])<0; j--){
                arr[j] =arr[j-1];
            }
            arr[j] =temp;
        }
    }

    public static <E extends Comparable<E>> void sort(E[] arr,int l,int r) {
        for (int i = l; i <= r; i++) {
            // 将 arr[i] 插入到合适位置
            // v3
            E temp = arr[i];
            int j;
            for (j = i; j-1 >= l && temp.compareTo(arr[j-1])<0; j--){
                arr[j] =arr[j-1];
            }
            arr[j] =temp;
        }
    }

    public static <E extends Comparable<E>> void sortV1(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将 arr[i] 插入到合适位置
            // v1
//            for (int j = i; j-1 >= 0; j--)
//                if (arr[j].compareTo(arr[j-1])<0)
//                    swap(arr,j,j-1);
//                else break;

            // v2
            for (int j = i; j-1 >= 0&&arr[j].compareTo(arr[j-1])<0; j--)
                swap(arr,j,j-1);
        }
    }

    public static <E extends Comparable<E>> void sortV2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将 arr[i] 插入到合适位置
            // v3
            E temp = arr[i];
            int j;
            for (j = i; j-1 >= 0 && temp.compareTo(arr[j-1])<0; j--){
                arr[j] =arr[j-1];
            }
                arr[j] =temp;
        }
    }

    private static <E>void swap(E[] arr, int i, int minDataIndex) {
        E temp = arr[i];
        arr[i] = arr[minDataIndex];
        arr[minDataIndex] =temp;
    }


    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n: dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            Integer[] arr2 = Arrays.copyOf(arr,arr.length);
//            SortingHelper.sortTest("InsertionSortV1",arr);
//            SortingHelper.sortTest("InsertionSortV2",arr2);

            System.out.println("Random Array: ");
            SortingHelper.sortTest("SelectionSort",arr);
            SortingHelper.sortTest("InsertionSort",arr2);

            System.out.println();
            System.out.println("Ordered Array: ");

            arr = ArrayGenerator.generateOrderedArray(n);
            arr2 = Arrays.copyOf(arr,arr.length);
            SortingHelper.sortTest("SelectionSort",arr);
            SortingHelper.sortTest("InsertionSort",arr2);
            System.out.println();

        }

    }
}
